题目分析

这个题目看起来很复杂，其实难度并不大，给小伙伴们一些提示，先补最小无法拼凑的数字。

贪心

什么是先补齐最小值呢？
以样例1来解释，我们数组中有[1,3]，而我们要凑齐1到6，因此从1开始看一看能否凑齐。1，3，4可以，2，5，6都不可以，这时我们肯定要补一个小于等于2的数，如果补大的数，那么2还是无法得到，因此先补最小的一定是最优的。那么补哪一个数合适呢？补1还剩补2呢？这时一定要补2。

这里给出结论，如果最小无法拼凑的数字为k，那么就补k一定是最优的。因为从1到k - 1都是可以拼凑的，那么补了k，从1到2k - 1都是可以拼凑的。这样范围是最大的。

如果没有拼凑的数字是k，数组中存在比k小的元素m，我们应该如何操作呢？我们可以使用m使得无法拼凑的最小数字变成k + m，这也非常好理解的。

以样例2来说明，[1,5,10]，令x是当前无法拼凑的最小值，初始值设为1，令idx = 0，代表当前已经用了多少个数字，当1无法获得的时候，我们先查数组中是否有小于等于x但是没有使用的元素，如果有，x += nums[idx++]，这句话的意思是可以用数组中的元素扩大范围。

那么无法拼凑的最小值为2，然后再查数组中是否有2，这里没有，那么需要补一个2，这时无法拼凑的最小值变为4。数组中也没有4，补一个4，这时无法拼凑的最小值为8。

这时发现有一个元素5小于等于8，没有用到，可以使用这个元素扩大范围，这时无法拼凑的最小值为8+5=13。这时发现10小于等于13，没有用到，可以进一步扩大范围到13+10=23。因此补2和4，可以最大实现到23都可以由数组中的数字表示。

算法的**时间复杂度为$O(log(n) + m)$，空间复杂度为$O(1)$**，其中n是要达到的正整数，m为数组中元素的个数。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long long x = 1;
        int idx = 0;
        int res = 0;
        while (x <= n) {
            if (idx < nums.size() && x >= nums[idx]) { x += nums[idx++]; }
            else { 
                x *= 2;
                res++;
            }
        }
        return res;
    }
};

刷题总结

数学问题可能需要我们开动脑筋，看一看补齐元素有什么规律，后来发现补齐小的元素一定是最优的，找到突破口，再慢慢修改调整代码即可。